#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution
{
private:
  vector<vector<int>> res;
  vector<int> track;

  // sum为每一次dfs的结果
  void backtrack(vector<vector<int>> &res, vector<int> &track, int sum, int begin, vector<int> candidates, int target)
  {
    if (sum > target)
      return;
    if (target == sum)
    {
      res.push_back(track);
      return;
    }

    for (int i = begin; i < candidates.size(); i++)
    {
      // 重点理解这里剪枝，前提是候选数组已经有序
      if (sum + candidates[i] > target)
      {
        break;
      }

      track.push_back(candidates[i]);
      cout << "递归之前=>";
      for (auto c : track)
      {
        cout << c << ",";
      }
      cout << "目前累加的和到了=" << sum + candidates[i];
      cout << endl;

      backtrack(res, track, sum + candidates[i], i, candidates, target); // 理解这里放i,进入递归还是i=0的子树，所以可以用的，但是进入第二层i=1的时候，此时i已经加1了避免了重复使用的情况
      track.pop_back();
      // track回溯即可，sum只是作为一个判断条件，如果sum>target或==target直接return就可以了

      cout << "递归之后=>";
      for (auto c : track)
      {
        cout << c << ",";
      }
      cout << endl;
    }
    return;
  }

public:
  vector<vector<int>> combinationSum(vector<int> candidates, int target)
  {
    int len = candidates.size();

    if (0 == len)
      return res;

    sort(candidates.begin(), candidates.end());

    backtrack(res, track, 0, 0, candidates, target);

    return res;
  }
};

int main()
{
  Solution solute;
  vector<int> candidate = {2, 3, 6, 7};
  int target = 7;
  solute.combinationSum(candidate, target);

  return 0;
}